package com.fr.lintcode;

import org.junit.Test;

public class Q1682 {

    /**
     * @param grid: 
     * @return: nothing
     */
    public int minimumPathSumIII(int[][] grid) {
        // 
    	if(grid == null || grid.length ==0 || grid[0].length == 0) {
    		return 0;
    	}
    	int m = grid.length;
    	int n = grid[0].length;
    	
    	int dp[][] = new int[m][n];
    	for(int i = 0; i < m ;i ++) {
    		for(int j = 0; j < n; j ++) {
    			if(i == 0&& j ==0) {
    				dp[i][j] = grid[i][j];
    			}else if(i == 0) {
    				dp[i][j] = dp[i][j -1] + grid[i][j];
    			}else if(j == 0) {
    				dp[i][j] = dp[i -1][j] + grid[i][j];
    			}else {
    				int min = Math.min(Math.min(dp[i -1][j], dp[i][j -1]), dp[i -1][j -1]);
    				dp[i][j] = min + grid[i][j];
    			}
    		}
    	}
    	return dp[m - 1][n - 1];
    }
    
    @Test
    public void testA() {
    	int [][]  grid = {{-2,-5,-3,-3,3,1,-2},{-5,3,-4,-5,-1,1,1},{3,0,-3,2,3,1,0},{-4,-3,-3,-5,-1,-2,3},{1,2,4,4,0,3,-1},{4,-3,0,1,1,-5,4},{-1,-5,-5,-5,3,-4,1},{-1,1,1,-5,-1,2,-4},{-4,3,2,3,-3,-5,-1}};
    	minimumPathSumIII(grid);
    }

}
